Юный программист
Саша написал свою первую тестирующую систему. Он так обрадовался тому, что она
скомпилировалась, что решил пригласить школьных друзей на свой собственный
контест.
Но в конце тура
выяснилось, что система не умеет сортировать команды в таблице результатов.
Помогите Саше реализовать эту сортировку.
Команды
упорядочиваются по правилам ACM:
·
по количеству решённых задач в порядке
убывания;
·
при равенстве количества решённых задач
– по штрафному времени в порядке возрастания;
·
при прочих равных – по номеру команды в
порядке возрастания.
Вход. Первая строка
содержит количество команд n (1
≤ n ≤ 105), участвующих в
контесте. В i-ой из следующих n строк записано количество решённых
задач s (0 ≤ s ≤ 100) и штрафное время t (0 ≤ t ≤ 105) команды с номером i.
Выход. Выведите n чисел – номера команд в
отсортированном порядке.
|
Пример входа |
Пример выхода |
|
5 3 50 5 720 1 7 0 0 8 500 |
5 2 1
3 4 |
сортировка
Команду будем
хранить в виде структуры:
·
номер команды;
·
штрафное время;
·
количество решенных задач;
Следует написать компаратор – функцию сравнения двух
команд участников согласно правил АСМ. После чего отсортировать команды.
Объявим
структуру команды – участника АСМ соревнования: номер команды, штрафное время и
количество решенных задач.
struct person
{
int id,
penalty_time, problems;
}
*acm;
Функция cmp – компаратор для
сортировки участников соревнования.
int
cmp(person a, person b)
{
Сортируем по количеству решённых задач в порядке убывания.
if
(a.problems != b.problems) return a.problems
> b.problems;
При равенстве
количества решённых задач – сортируем по штрафному времени в порядке возрастания.
if
(a.penalty_time != b.penalty_time)
return
a.penalty_time < b.penalty_time;
При прочих равных – сортируем по номеру команды в порядке
возрастания.
return a.id
< b.id;
}
Основная часть
программы. Выделяем память под массив команд.
scanf("%d",&n);
acm
= new person[n];
Считываем данные о командах.
for(i
= 0; i < n; i++)
{
scanf("%d
%d",&acm[i].problems,&acm[i].penalty_time);
acm[i].id = i + 1;
}
Сортируем команды согласно заданного условия.
sort(acm,acm+n,cmp);
Выводим номера команд в порядке их расположения в таблице
результатов.
for(i
= 0; i < n; i++)
printf("%d",acm[i].id);
printf("\n");
delete[] acm;
Реализация
алгоритма – вектор
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
int
n, i, ptr;
struct person
{
int id,
penalty_time, problems;
};
vector<person>
acm;
int
cmp(person a, person b)
{
if
(a.problems != b.problems) return a.problems
> b.problems;
if
(a.penalty_time != b.penalty_time)
return
a.penalty_time < b.penalty_time;
return a.id
< b.id;
}
int
main(void)
{
scanf("%d",&n);
acm.resize(n);
for(i = 0; i
< n; i++)
{
scanf("%d
%d",&acm[i].problems,&acm[i].penalty_time);
acm[i].id = i + 1;
}
sort(acm.begin(),acm.end(),cmp);
for(i = 0; i
< n; i++)
printf("%d
",acm[i].id);
printf("\n");
return 0;
}
#include <cstdio>
#include <algorithm>
using namespace std;
int
n, i, ptr;
struct person
{
int id,
penalty_time, problems;
int operator< (const
person &a) const
{
if
(problems != a.problems) return problems >
a.problems;
if
(penalty_time != a.penalty_time)
return penalty_time < a.penalty_time;
return id
< a.id;
}
}
*acm;
int
main(void)
{
scanf("%d",&n);
acm = new
person[n];
for(i = 0; i
< n; i++)
{
scanf("%d
%d",&acm[i].problems,&acm[i].penalty_time);
acm[i].id = i + 1;
}
sort(acm,acm+n);
for(i = 0; i
< n; i++)
printf("%d
",acm[i].id);
printf("\n");
delete[] acm;
return 0;
}
Java реализация
import java.util.*;
class Person
{
int problems;
int penalty_time;
int id;
public Person(int problems, int penalty_time, int id)
{
this.problems = problems;
this.penalty_time = penalty_time;
this.id = id;
}
}
public class Main
{
public static class MyFun implements Comparator<Person>
{
public int
compare(Person a, Person b)
{
if (a.problems == b.problems && a.penalty_time == b.penalty_time) return a.id - b.id;
if (a.problems == b.problems) return a.penalty_time - b.penalty_time;
return b.problems - a.problems;
}
}
public static void main(String[] args)
{
Scanner con = new Scanner(System.in);
int n = con.nextInt();
Person[] p = new Person[n];
for (int i = 0; i < n; i++)
p[i] = new Person(con.nextInt(), con.nextInt(), i+1);
Arrays.sort(p, new MyFun());
for (int i = 0; i < n; i++)
System.out.print(p[i].id + " ");
con.close();
}
}